翻訳と辞書 Words near each other ・ Dense (film) ・ Dense artery sign ・ Dense bodies ・ Dense connective tissue ・ Dense granule ・ Dense graph ・ Dense heterarchy ・ Dense Inert Metal Explosive ・ Dense irregular connective tissue ・ Dense non-aqueous phase liquid ・ Dense order ・ Dense Pack ・ Dense plasma focus ・ Dense regular connective tissue ・ Dense set ・ Dense subgraph ・ Dense submodule ・ Dense Time ・ Dense-in-itself ・ Dense-rock equivalent ・ Dense-scale lantern shark ・ Denseisha ・ Densely defined operator ・ Densely packed decimal ・ Densen Audio Technologies ・ Densen Uta ・ Densetsu no Shōjo ・ Densetsu no Stafy (video game) ・ Densetsu no Stafy 2 ・ Densetsu no Stafy 3 Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Dense subgraph ： ウィキペディア英語版 Dense subgraph In computer science the notion of highly connected subgraphs appears frequently. This notion can be formalized as follows. Let $G=(E,V)$ be an undirected graph and let $S=(E\_S,V\_S)$ be a subgraph of $G$. Then the ''density'' of $S$ is defined to be $d(S)\; =$. The densest subgraph problem is that of finding a subgraph of maximum density. In 1984, Andrew V. Goldberg developed a polynomial time algorithm to find the maximum density subgraph using a max flow technique. ==Densest $k$ subgraph== There are many variations on the densest subgraph problem. One of them is the densest $k$ subgraph problem, where the objective is to find the maximum density subgraph on exactly $k$ vertices. This problem generalizes the clique problem and is thus NP-hard in general graphs. There exists a polynomial algorithm approximating the densest $k$ subgraph within a ratio of $n^$ for every $\backslash epsilon\; >\; 0$,〔http://dl.acm.org/citation.cfm?id=1806719〕 while it does not admit PTAS unless $NP\; \backslash subseteq\; \backslash bigcap\_\; BPTIME(2^)$.〔http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.114.3324〕 The problem remains NP-hard in bipartite graphs and chordal graphs but is polynomial for trees and split graphs. It is open whether the problem is NP-hard or polynomial in (proper) interval graphs and planar graphs (notice that the connected version of the problem remains NP-hard in planar graphs 〔https://cs.uwaterloo.ca/~brecht/papers/jcmcc-1991.pdf〕). 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Dense subgraph」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.